package LeetCode.month01.day31;


import java.util.regex.Pattern;

public class No2106 {
    public static void main(String[] args) {
        System.out.println(maxTotalFruits(new int[][]{{0,10000}},200000,5));
    }
    public static int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int n = fruits.length;
        int left = lowerBound(fruits,startPos-k);
        int right = left;
        int sum = 0;
        for (; right < n&&fruits[right][0]<=startPos; right++) {
            sum+=fruits[right][1];
        }
        int res = sum;
        for (; right < n&&fruits[right][0]<=startPos+k; right++) {
            sum+=fruits[right][1];
            while(fruits[right][0]*2-startPos-fruits[left][0]>k
                    &&fruits[right][0]+startPos-fruits[left][0]*2>k){
                sum-=fruits[left][1];
                left++;
            }
            res = Math.max(sum,res);
        }
        return res;
    }

    public static int lowerBound(int[][] fruits,int index){
        int left = 0;
        int right = fruits.length-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(fruits[mid][0]<index){
                left=mid+1;
            }else{
                right = mid-1;
            }
        }
        return left;

//        int left = -1;
//        int right = fruits.length; // 开区间 (left, right)
//        while (left + 1 < right) { // 开区间不为空
//            // 循环不变量：
//            // fruits[left][0] < target
//            // fruits[right][0] >= target
//            int mid = left + (right - left) / 2;
//            if (fruits[mid][0] < index) {
//                left = mid; // 范围缩小到 (mid, right)
//            } else {
//                right = mid; // 范围缩小到 (left, mid)
//            }
//        }
//        return right;
    }
}
